import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by L.jp
 * Description:在给定的网格中，每个单元格可以有以下三个值之一：
 *
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 *
 * 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
 *
 * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。

 * User: 86189
 * Date: 2021-11-29
 * Time: 11:17
 */
/*
       1.bfs一般使用队列解决问题，在这里用队列先存储数组表示所有的腐烂橘子的坐标
       2.遍历腐烂橘子的同时，记录新鲜橘子的个数，同时定义最小步数为0
       3.求出队列长度，遍历队列一个一个把腐烂橘子的坐标弹出，然后利用定义的周围数组遍历他的周围，在坐标合法并且周围有新鲜橘子的情况下，把新鲜的橘子污染，四个周围是同时污染的，污染后让步数加1，
       4.污染新鲜橘子的同时，新鲜的橘子数量也会减少，继续把新一轮的腐烂的橘子入队
       5.遍历完队列之后，如果新鲜橘子的数量不会等于0，那么表示新鲜的橘子并没有被全部消除，返回-1，如果等于0，则返回步数
 */
public class RottenOrange {
    public static int orangesRotting(int[][] grid){
        int[][] nextPos={{-1,0},{0,1},{1,0},{0,-1}};
        if(grid.length==0){
            return -1;
        }
        int n=grid.length;
        int m=grid[0].length;
        int newCount=0;//记录新的橘子数量
        Queue<int[]> queue=new LinkedList<>();//定义队列存储只含有两个元素的数组腐烂橘子的坐标，
        //
        for(int x=0;x<n;x++){
            for(int y=0;y<m;y++){
                if(grid[x][y]==1)
                    newCount++;
                if(grid[x][y]==2)
                    queue.offer(new int[]{x,y});//每遍历到一个腐烂橘子就要新建一个数组表示一个腐烂橘子的坐标
            }
        }
        int step=0;//记录将所有新鲜橘子变为腐烂橘子的最小分钟数
        while(newCount>0 && !queue.isEmpty()){
            step++;
            int size= queue.size();//求得第一轮腐烂橘子的个数，并且弹出他，去遍历他的上下左右周围，去污染新鲜的橘子，然后再把被污染的橘子入列。。。循环
            for(int i=0;i<size;i++){
                int[] oldOrange=queue.poll();//一个一个的弹出腐烂橘子的坐标
                //遍历他的周围
                for(int j=0;j<4;j++){
                    int nx=oldOrange[0]+nextPos[j][0];//新的被腐烂的横坐标
                    int ny=oldOrange[1]+nextPos[j][1];//j表示按照上下左右的顺序的第几个，0和1表示横坐标和纵坐标
                    //求得的周围坐标中，如果有腐烂的橘子就不污染，有新的橘子就要污染
                    if(nx>=0 && nx<n &&  ny>=0 && ny<m &&  grid[nx][ny]==1){//周围的坐标要合法，并且当前坐标是新鲜的橘子才要被污染
                        grid[nx][ny]=2;//被标记为腐烂橘子
                        newCount--;//新鲜的橘子减1
                        queue.offer(new int[]{nx,ny});//每腐烂一个橘子就要把他入列，以便进行下一次的广搜
                    }
                }
            }
        }
        //遍历完队列之后，如果总的矩阵中还有新鲜的橘子，那么就返回-1
        if(newCount>0){
            return -1;
        }else{
            return step;
        }

    }

    public static void main(String[] args) {
        int[][] grid={{2,1,1},{1,1,0},{0,1,1}};
        System.out.println(orangesRotting(grid));
    }
}
